package com.LeeCode;

/**
 * 查找给定哈希值的子串
 */

public class Code2156 {
    public static void main(String[] args) {
        String s = "fbxzaad";
        int power = 31, modulo = 100, k = 3, hashValue = 32;
        System.out.println(new Code2156().subStrHash(s, power, modulo, k, hashValue));
    }

    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        // 用秦九韶算法计算 chars[n-k:] 的哈希值，同时计算 pk=power^k
        long hash = 0;
        long pk = 1;
        for (int i = n - 1; i >= n - k; i--) {
            hash = (hash * power + (chars[i] & 31)) % modulo;
            pk = pk * power % modulo;
        }
        int ans = hash == hashValue ? n - k : 0;
        // 向左滑窗
        for (int i = n - k - 1; i >= 0; i--) {
            // 计算新的哈希值，注意 +mod 防止计算出负数
            hash = (hash * power + (chars[i] & 31) - pk * (chars[i + k] & 31) % modulo + modulo) % modulo;
            if (hash == hashValue) {
                ans = i;
            }
        }
        return s.substring(ans, ans + k);
    }
}
